package com.lwg.datastructure.dynamicPrograming;

/**
 * @FileName: Plunder2.java
 * @Description: 打家劫舍2
 * @author: 李炜光
 * @slogan:
 * @Date: 2022/2/18
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * 分析：
 * 1. 如果只有一间房屋，则dp[0] = nums[0];
 * 2. 如果有两间房屋，则dp[1] = Math.max(nums[0],nums[1]);
 * 3. 当房间数比较多时，偷窃范围[0,n-2] 和 [1,n-1]，利用dp[i]=Math.max(dp[i-2]+ nums[i],dp[i-1])
 * 分别计算两个时间段的最大值 比较，得到最终结果
 */
public class Plunder2 {

    public int rob(int[] nums) {
        int length = nums.length;
        if (length == 1) {
            return nums[0];
        }
        int dp[] = new int[length + 1];
        dp[0] = nums[0];
        if (length == 2) {
            return dp[1] = Math.max(dp[0], nums[1]);
        }
        //return Math.max(robTwo(nums, 0, length - 2), robTwo(nums, 1, length - 1));
        return Math.max(robTwo2(nums, 0, length - 2), robTwo2(nums, 1, length - 1));
    }

    public int robTwo(int[] nums, int start, int end) {
        int dp[] = new int[end - start + 2];
        dp[start] = nums[start];
        dp[start + 1] = Math.max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[end];
    }

    public int robTwo2(int[] nums, int start, int end) {
        int first = nums[start];
        int second = Math.max(first, nums[start+1]);
        for (int i = start + 2; i <= end; i++) {
            int temp = second;
            second = Math.max(first + nums[i], second);
            first = temp;
        }
        return second;
    }
}

class MainClass9 {
    public static int[] stringToIntegerArray(String input) {
        input = input.trim();
        input = input.substring(1, input.length() - 1);
        if (input.length() == 0) {
            return new int[0];
        }

        String[] parts = input.split(",");
        int[] output = new int[parts.length];
        for (int index = 0; index < parts.length; index++) {
            String part = parts[index].trim();
            output[index] = Integer.parseInt(part);
        }
        return output;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while ((line = in.readLine()) != null) {
            int[] nums = stringToIntegerArray(line);

            int ret = new Plunder2().rob(nums);

            String out = String.valueOf(ret);

            System.out.print(out);
        }
    }
}